//给出一组数，可以在任何一个数前加'+' 或‘-’，求使得其和为target的组合有多少种
//可以将这个问题转化为背包问题
/*
假设有两个数集，positive和negative，前者存放加正号的，后者存放加负号的,这俩都是正数集合
那么positive+negative=sum;positive-negative=target;
那么positive=(sum+target)/2
意思是从数组里面找出一个数集，其和等于positive数集之和就是找到了正确的组合

问题就变成了背包问题：从数组中找数字，使其和为positive
*/

/*
使用一维dp数组
dp[j]表示数之和为j的组合数
那么dp[0]=1,只要一个0
物品的重量价值都为nums[i]
dp递推：若数字nums[i]，那么只需dp[i-nums[i]]种方法，因为加上nums[i]即可
那么dp[j]就等于从nums[i]到j的dp之和
1 1 1 2 1 
如dp[5]=dp[4]+dp[3](遍历所有数字)
因此遍历顺序也是先遍历数组，再遍历背包，并且背包要倒序
*/
#include <vector>
#include <cmath>
using std::abs;
using std::vector;
int findTargetSumWays(vector<int>& nums, int target){
    int sum=0;
    for(int i=0;i<nums.size();i++)
        sum+=nums[i];
    if(sum<abs(target)||(sum+target)%2==1) return 0;        //两种无组合条件
    int bagSize=(sum+target)/2;
    vector<int> dp(bagSize+1);
    dp[0]=1;
    for(int i=0;i<nums.size();i++){     //遍历物品
        for(int j=bagSize;j>=nums[i];j--)   //遍历背包
            dp[j]+=dp[j-nums[i]];
    }
    return dp[bagSize];
} 
